package sort.LinkedList;

import struct.ListNode;

/**
 * @description:
 * <br>链表归并排序（自顶向下，快排）
 * <br>时间复杂度： O(nlogn)
 * <br>空间复杂度： O(logn)
 * @author: mayunfei
 * @date: 2024/12/26 20:23
 */
public class LinkedListMergeSortT2D implements LinkedListSort {

    @Override
    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    private ListNode sort(ListNode head, ListNode tail) {
        if (head == null) return null;
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode left = sort(head, mid);
        ListNode right = sort(mid, tail);
        return merge(left, right);
    }

    // 有序列表排序
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode tmp = dummy;
        ListNode tmp1 = l1;
        ListNode tmp2 = l2;
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val < tmp2.val) {
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            } else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        if (tmp1 != null) tmp.next = tmp1;
        if (tmp2 != null) tmp.next = tmp2;
        return dummy.next;
    }
}
